#pragma once

#include "templatevector.h"

/**
 * simple templated vector. Ideal for dynamic lists of primitive types and single pointers.
 * @WARNING template with virtual types, or types that will be pointed to at your own risk!
 * @author mvaganov@hotmail.com December 2009
 */
template<typename DATA_TYPE>
class TemplateVectorSpecialSort : public TemplateVector<DATA_TYPE>
{
public:
	typedef bool (*BinaryOperator)(DATA_TYPE const & a_param0, DATA_TYPE const & a_param1);
private:
	/** the mechanism for telling if one term belongs before another */
	BinaryOperator m_fpCorrectOrder;
	/** the mechanism for telling if one term is the same as another */
	BinaryOperator m_fpEqualTo;

	static bool S_LessThan(DATA_TYPE const & a_left, DATA_TYPE const & a_right){return a_left < a_right;}
	static bool S_EqualTo(DATA_TYPE const & a_left, DATA_TYPE const & a_right){return a_left == a_right;}
public:
	inline bool lessThan(DATA_TYPE const & a_left, DATA_TYPE const & a_right)
	{
		return m_fpCorrectOrder(a_left, a_right);
	}
	inline bool equalTo(DATA_TYPE const & a_left, DATA_TYPE const & a_right)
	{
		return m_fpEqualTo(a_left, a_right);
	}
	void setSortingMechanism(BinaryOperator const & a_sortMechanism, BinaryOperator const & a_equalTo)
	{
		m_fpCorrectOrder = a_sortMechanism;
		m_fpEqualTo = a_equalTo;
	}

	/** sets all fields to an initial data state. WARNING: can cause memory leaks if used without care */
	void init()
	{
		TemplateVector::init();
		setSortingMechanism(S_LessThan, S_EqualTo);
	}

	/** @return true of the copy finished correctly */
	inline bool copy(TemplateVectorSpecialSort<DATA_TYPE> const & a_vector)
	{
		bool copied = TemplateVector::copy(a_vector);
		if(copied)
		{
			setSortingMechanism(a_vector.m_fpLessThan, a_vector.m_fpEqualTo);
		}
		return copied;
	}

	/** copy constructor */
	inline TemplateVectorSpecialSort(
		const TemplateVector<DATA_TYPE> & a_vector)
	{
		init();
		copy(a_vector);
	}

	/** default constructor allocates no list (zero size) */
	inline TemplateVectorSpecialSort(){init();}

	/** format constructor */
	inline TemplateVectorSpecialSort(int const & a_size,
		const DATA_TYPE & a_defaultValue)
	{
		init();
		ensureCapacity(a_size);
		for(int i = 0; i < a_size; ++i)
			add(a_defaultValue);
	}
	int indexOfSortedInsert(DATA_TYPE const & a_value) const
	{
		int index;
		if(!m_size || m_fpCorrectOrder(a_value, get(0)))
		{
			index = 0;
		}
		else if(!m_fpCorrectOrder(a_value, get(m_size-1)))
		{
			index = m_size;
		}
		else
		{
			int first = 0, last = m_size;
			while (first <= last)
			{
				index = (first + last) / 2;
				if (m_fpCorrectOrder(a_value, m_data[index])) 
					last = index - 1;
				else if (m_fpEqualTo(a_value, m_data[index])) 
					break;
				else //if (!m_fpCorrectOrder(a_value, m_data[index])) 
					first = index + 1;
			}
			if(!m_fpCorrectOrder(a_value, m_data[index])
			&& !m_fpEqualTo(a_value, m_data[index]))
				index++;
		}
		return index;
	}
	/**
	 * uses binary sort to put values in the correct index. safe if soring is always used
	 * @param a_value value to insert in order
	 * @param a_allowDuplicates will not insert duplicates if set to false
	 * @return the index where a_value was inserted
	 */
	int insertSorted(DATA_TYPE const & a_value, bool const & a_allowDuplicates)
	{
		int index = indexOfSortedInsert(a_value);
		if(!m_size  || a_allowDuplicates
		|| !m_fpEqualTo(a_value, m_data[index]))
			insert(index, a_value);
		return index;
	}
	/**
	 * will only work correctly if the TemplateVector is sorted.
	 * @return the index of the given value, -1 if the value is not in the list
	 */
	int indexOfWithBinarySearch(const DATA_TYPE & a_value, const int & a_first, const int & a_limit)
	{
		if(m_allocated)
		{
			int first = a_first, last = a_limit;
			while (first <= last && first != a_limit)
			{
				int mid = (first + last) / 2;  // compute mid point.
				if (m_fpCorrectOrder(a_value, m_data[mid])) 
					last = mid - 1; // repeat search in bottom half.
				else if(m_fpEqualTo(a_value, m_data[mid]))
					return mid;     // found it. return position
				else //if (!m_fpCorrectOrder(a_value, m_data[mid])) 
					first = mid + 1;  // repeat search in top half.
			}
		}
		return -1;    // failed to find key
	}

	int indexOfWithBinarySearch(const DATA_TYPE & a_value)
	{
		return indexOfWithBinarySearch(a_value, 0, m_size);
	}

	bool isSorted()
	{
		bool sorted = true;
		for(int i = 1; sorted && i < size(); ++i)
		{
			sorted = m_fpCorrectOrder(get(i-1), get(i));
		}
		return sorted;
	}
};